• CPU Scheduling
• Page Replacement in OS
• Disk Scheduling

Operating System

CPU Scheduling

CPU Scheduling

CPU scheduling is the process by which an operating system decides which process (or thread) gets to use the CPU next and for how long. Since many programs may be ready to run at the same time, the CPU scheduler ensures they share the processor efficiently.

A computer often has multiple programs running simultaneously. Because a CPU can execute only one process at a time (per core), the operating system must decide:

• Which process runs next.
• How long it runs.
• When to switch to another process.

The goals of CPU scheduling are to:

• Maximize CPU utilization.
• Increase system throughput (more work completed).
• Minimize waiting time.
• Minimize turnaround time.
• Reduce response time for interactive users.
• Ensure fairness among processes.

How CPU scheduling works?

• Processes enter the ready queue.
• The CPU scheduler selects one process from the queue.
• The selected process executes on the CPU.
• When it finishes, blocks for I/O, or its time slice expires, the scheduler chooses another process.

Types of CPU Scheduling

Non-Preemptive Scheduling

Once a process gets the CPU, it continues until it finishes or blocks for I/O. Example: First Come, First Served (FCFS).

Advantages:

• Simple to implement.
• Low overhead.

Disadvantages:

• Long processes can delay shorter ones.

Preemptive Scheduling

The operating system can interrupt a running process and assign the CPU to another process. Example: Round Robin (RR).

Advantages:

• Better response time.
• More suitable for interactive systems.

Disadvantages:

• More context switching overhead.

FCFS Scheduling

Process	Arrival Time	Burst Time
P1	0	8
P2	1	4
P3	2	2
P4	3	5
P5	4	3

Since all processes arrive in the order P1-> P2->P3 -> P4 -> P5, FCFS executes them in that order:

Gantt chart

0        8       12      14       19      22
|   P1   |   P2   |  P3  |   P4   |  P5   |    

• Turnaround Time (TAT) = CT - AT
• Waiting Time (WT) = TAT - BT

Process	AT	BT	CT	TAT	WT
P1	0	8	8	8	0
P2	1	4	12	11	7
P3	2	2	14	12	10
P4	3	5	19	16	11
P5	4	3	22	18	15
				8.6	13

Non-Preemptive SJF

Process	Arrival Time	Burst Time
P1	0	7
P2	2	4
P3	4	1
P4	5	4

At time 0, only P1 has arrived, so P1 executes first. At time 7, P2, P3, and P4 are available. P3 has the shortest burst time, so P3 executes ntext. The P2 and P4 both have 4ms. We choose P2 first because it arrived earlier.

0        7    8        12       16
|   P1   | P3 |   P2   |   P4   |

0

Process	AT	BT	CT	TAT = CT-AT	WT = TAT-BT
P1	7	7	7	0
P1	4	1	8	4	3
P3	2	4	12	10	6
P4	5	4	16	11	7
				8ms	4ms

Round Robin Scheduling

Process	Burst time
P1	10
P2	5
P3	8
P4	6

All arrive at time 0. Time Quantum = 3ms

0    3    6    9    12   15   18   21   23   26   29
| P1 | P2 | P3 | P4 | P1 | P2 | P3 | P4 | P1 | P3 |

Let's calculate carefully:

• P1: 10 -> remaining 7
• P2: 5 -> remaiing 2
• P3: 8 -> remaiing 5
• P4: 6 -> remaining 3
• P1: 7 -> remaining 4
• P2: 2 -> finishes at 17
• P3: 5 -> remaining 2
• P4: 3 -> finishes at 23
• P1: 4 -> remaining 1
• P3: 2 -> finishes at 28
• P1: 1 -> finishes at 29

Gantt Chart

0    3    6    9    12   15   17   20   23   26   28   29
| P1 | P2 | P3 | P4 | P1 | P2 | P3 | P4 | P1 | P3 | P1 |

Completion Time

Process	BT	CT	TAT	WT
P1	10	29	29	19
P2	5	17	17	12
P3	8	28	28	20
P4	6	23	23	17
			24.25ms	17ms

Priority Scheduling

Process	Burst Time	Priority
P1	10	3
P2	1	1
P3	2	4
P4	1	2

Smaller number = higher priority

Therefore execution order is:
P2 -> P4 -> P1-> P3

Gantt Chart

0    1    2          12    14
| P2 | P4 |    P1    | P3 |

All processes arrive at time 0.

Process	BT	CT	TAT	WT
P2	1	1	1	0
P4	1	2	2	1
P1	10	12	12	2
P3	2	14	14	12
			7.25ms	3.75ms

TAT = CT - AT

WT = TAT = BT

Average WT = sumation(WT)/Number of Processes

Average TAT = sumation(TAT)/Number of Processes